The present invention relates in general to network communications switching, and more particularly to synchronizing store-and-forward networks and scheduling real-time or high-priority network transmissions for immediate and direct layer one or physical level switching.
Current applications are consuming network bandwidth at exponentially increasing rates Current packet-switching, cell-switching, frame-switching, and other store-and-forward communication networks were designed to provide high-efficiency routing and switching capability for bursty, non-periodic, non-predictable, non-time-sensitive data traffic. However, when attempting to deliver continuous, periodic, predictable, time-sensitive, or urgent information, the store-and-forward style architectures are by their nature, ill-suited to efficiently perform the task. This is because store-and-forward style architectures, by their innate design, first store data, then examine it for addressing and priority, then switch and route it based on priority, then store the data again in various priority queues, and then transmit it to the next switch to repeat the process. These steps are subject to varying slowdowns and delays based on continuously varying, unpredictable network congestion. On the other hand, by its very different nature, continuous, periodic, predictable, time-sensitive, and high-priority information requires immediate switch-through with no delays. Thus, the characteristics which make store-and-forward switching so efficient for bursty, non-periodic, non-predictable, non-time-sensitive data, are the exact opposite of what is needed for continuous, periodic, predictable, time-sensitive, or high-priority information.
As a result of this dilemma, various complicated schemes have been devised in an attempt to compensate for and circumvent these underlying store-and-forward network characteristics. Examples of these schemes include, but are not limited to prioritization schemes, priority queuing mechanisms, constant and variable bit rates, guaranteed and peak bit rates, layer three switching, guaranteed throughput, faster routing, Gigabit routing, switch routing, etc. Yet each of these attempts to circumvent the store-and-forward dilemma still remains built upon the fundamental store-and-forward architecture and switching. The result of these attempts to resolve the problem is a combination of solutions with complicated protocols, complex implementation schemes, and/or inefficient use of network resources.
The explosion of bursty, non-periodic, non-predictable, non-time-sensitive data traffic coupled with converging high-bandwidth, real-time applications over these store-and-forward style packet-, cell-, and frame-based networks inevitably results in network congestion, delays, inconsistent delivery, jitter, packet loss, quality of service degradation, and/or inefficient networks. The applications most noticeably affected will be real-time applications and high-priority information.
Real-time applications are defined as applications where the end user experiences the information in real-time as it flows over the network. Examples of real-time applications are telephony, Internet phone, packet phone video conferencing, video streaming, audio streaming, broadcast, multicast, and any other multimedia streaming applications. Real-time applications may be periodic, predictable, or time-sensitive.
High-priority information is defined as information that must be delivered more quickly, more reliably, more accurately, and ahead of other lower-priority information in the network. Examples of high-priority information include, but are not limited to emergency messages, time-sensitive or time-dependent information, network control messages, guaranteed delivery messages, or any other information deemed more important or more urgent for various reasons.
Real-time applications and high-priority information are dependent upon the rapid, consistent, on-time, non-blocked, non-delayed, non-congested, loss-less, jitter-free, reliable flow of data in real-time. With real-time applications and high-priority information, poor network performance resulting in time delays and quality loss can drastically degrade the quality of the end user experience and the value of the service. At the same time, network operators and administrators would like to avoid network complexities and inefficiencies in delivering real-time applications and high-priority information. These delays, degradation, inefficiencies, and complexities are what this invention seeks to overcome.
Several factors can cause real-time applications such as Internet phone, Internet Video phone, Internet Video Conferencing, Internet Streaming Audio, Internet Streaming Video, and other real-time multimedia applications to suffer in both quality and time delays over packet, cell, or frame-oriented store-and-forward networks. Among them are:
Packet, cell, and frame discard due to a congested switch, which in turn results in dropout glitches (poor quality) and/or increased delay time to retransmit missing packets, cells, or frames.
Packet loss due to alternate routing, which in turn results in dropout glitches (poor quality) and increased processing time to recover from and reconstruct missing packets.
Waiting for alternate path packets to arrive, resulting in time delays.
Reordering of packets that arrive out-of-order, resulting in time delays.
Higher layer processing (layers 2-4) of packets at each router before routing the packets on to the next destination, resulting in time delays.
Loaded/congested networks which slow down packet, cell, or frame delivery, resulting in random, non-predictable time delays. This includes loading, congestion, and/or contention in shared-media networks such as CSMA/CD, Ethernet, Token-Ring, Aloha, shared wireless, or any other shared media contention which may cause congestion or delays. This also includes loading, congestion, and/or contention for resources inside a switch, router, or any other communications device, including but not limited to: input lines, input queues, priority queues, address lookup mechanisms, priority lookup mechanisms, switching fabrics, output queues, output lines, or any other resource sharing mechanisms in data switching or routing.
Some combination or all of these problems are innate in packet, cell, and frame-oriented networks, their architectures, switches, and protocols. This includes older systems as well as the newer standards like TCP/IP version 6, Frame Relay, and ATM. Newer protocols and systems such as Resource Reservation Protocol (RSVP), Bit Stream Reservation Techniques, layer two Switching, layer three Switching, Cut-though switching, Flow Switching and other techniques have been designed in an attempt to reduce these problems for real-time or high-priority information. However, none of these efforts have been able to completely eliminate a fundamental architectural tenet of packet, cell, and frame-based switching in store-and-forward networksxe2x80x94i.e., when network buffers get overloaded, these systems must drop packets and slow down to xe2x80x9cdecongest.xe2x80x9d This can affect and slow down real-time applications and high-priority information. For example, in some of these efforts, once a real-time packet is in the input buffer, it can be routed through even a congested switch with a higher priority. However, if the input buffers are fill, the real-time application may not be able to get its packet in to be recognized as a high-priority packet. On the other hand, efforts to overcome this problem by reserving capacity on the switch means the switch will, in effect, limit its input or throughput to reserve capacity for guaranteed applications, thus resulting in inefficiencies in the switch.
Streaming broadcast or multicast audio and video applications deal with these store-and-forward effects by having large buffers and error correction at the receiving end (client) to compensate for the uncontrollable delays and losses. However, the large buffers result in long start-time delays for both audio and video xe2x80x9cbroadcast-stylexe2x80x9d streaming applications. The end user must wait while the buffers fill with the initial incoming packets before he/she can see or hear the program.
Internet Phone, Internet Video Phone, and Internet Video Conferencing applications must reduce the size of these buffers to minimize the awkward delay time between end-users. They also use compression algorithms to reduce network congestion. Unfortunately, neither of these techniques is sufficient, since network overload and congestion will still cause packet discarding, slowdown, and jitter, enough to cause awkward pauses between end-users. The resulting conversation is similar to the delayed satellite conversations that are sometimes encountered in overseas calls. As mentioned previously, techniques to solve these problems, such as guaranteed constant bit rate or guaranteed peak bit rate, either introduce their own inefficiencies or don""t really guarantee the results one hundred percent of the time.
Newer networks are proposing to switch at very high gigabit speeds to minimize the delay times for real-time applications such as telephony. Nevertheless, as more high-bandwidth applications like telephony, web graphics, and streaming video get dumped into these gigabit networks, they too, will either be designed to be inefficient, or will get congested and slow down with the resulting degradation of speed and quality.
Clearly, there is a need for a way to:
guarantee delivery of selected packets, such as real-time and high-priority packets, like Internet phone, audio and video streaming, video conferencing, and urgent messages.
assure that selected packets, such as real-time and high-priority packets, arrive on time so that large buffers, long start delays, and awkward pauses are reduced or eliminated.
assure that selected packets with higher priority will be delivered more rapidly through the network than lower-priority packets.
overcome or bypass the packet networks"" innate characteristic of slowing down the delivery of specific packets when the network gets loaded or congested.
do the above tasks with a high degree of network efficiency.
The foregoing problems are solved and a technical advance is achieved in accordance with the principles of this invention as disclosed in several structural embodiments of switching devices, methods, and network architectures. These device embodiments, methods, and network architectures utilize means for a master clock, means for synchronization of clocks in distributed network elements; means for switching within each network element in a non-blocking, non-delaying manner at a layer one level; means for scheduling and executing high-priority, real-time, or other layer one calls or sessions in each network element; means for controlling said synchronization means, said switching means, and said scheduling and execution means in each network element; and the resulting system or network architecture wherein all layer one network element inputs and outputs on a given path switch their packets, cells, or frames in a cut-through manner bypassing the entire network at a layer one or physical level at the correct scheduled time with minimal or no store-and-forward delays.
More simply put, all of the store-and-forward device embodiments in the network are synchronized. Then a source or destination sets up a reservation schedule with all of the network devices for transmitting real-time or high-priority packets. At the specific predetermined scheduled time, all of the devices on the scheduled path through the network switch the appropriate input and output lines to bypass their standard store-and-forward switches and switch open a direct non-blocking, non-delaying layer one physical connection from one end of the network to the other. The specific scheduled packets are then transmitted into one end of the network where they propagate directly through all of the layer one switches on the path to the other end of the network, with no delays other than transmission line and layer one switch propagation delays. In this way, they completely bypass the store-and-forward network with all of its inherent disadvantages for continuous, periodic, predictable, time-sensitive, or high-priority information. Once the packets have been sent all the way through the network and the scheduled layer one event is over, the devices switch back to standard store-and-forward switching for bursty, non-periodic, non-predictable, non-time-sensitive, and non-high-priority information. In this way, the system works to optimum advantage and efficiency for each of the two types of data and switching methods.
The network architecture itself consists of means for a master clock, time synchronization receiver means for synchronizing a clock on each network element; a source, which is a network element, also variously termed an originator or a caller; a departure router, which is a network element, also variously termed a departure switch, a departure node, or an originating edge node; mid-destination routers, which are network elements, also variously termed mid-destination switches, internal nodes, or middle nodes; a final destination router, which is a network element, also variously termed a final-destination switch, or terminating edge node; a receiver which is a network element, also termed a called party; and transmission paths connecting the network elements.
The architecture is such that a master clock synchronizes the device embodiments using receiving synchronization means. In the preferred embodiment, the master clock comprises the combined master clocks on the satellite Global Positioning System (GPS) commonly used today for timing and positioning measurements. GPS enables synchronization of device embodiment clocks down to the microsecond and nanosecond range. Descriptions of GPS timing techniques and the accuracies obtainable are covered in xe2x80x9cTom Logsdon""s xe2x80x9cUnderstanding the Navstar: GPS, GIS, and IVHSxe2x80x9d; 2nd edition; 1995; Van Nostrand Reinhold; Ch. 11; pp.158-174 which is hereby incorporated by reference.
Detailed descriptions of GPS, synchronization techniques, time codes, clock measurements, accuracies, stabilities, and other useful applications of GPS technology are covered in literature from the company TrueTime, Inc, 2835 Duke Court, Santa Rosa, Calif. 95407, including Application Note #7, xe2x80x9cAffordable Cesium Accuracyxe2x80x9d; Application Note #11, xe2x80x9cVideo Time and Message Insertionxe2x80x9d; Application Note #12, xe2x80x9cMulti User Computer Time Synchronizationxe2x80x9d; Application Note #14, xe2x80x9cModel GPS-DC Mk III Oscillator Selection Guidexe2x80x9d; Application Note #19, xe2x80x9cSimplified Frequency Measurement Systemxe2x80x9d; Application Note #20, xe2x80x9cAchieving Optimal Results with High Performance GPSxe2x80x9d; Application Note #21, xe2x80x9cModel XL-DC in Frequency Control Applicationsxe2x80x9d; Application Note #22, xe2x80x9cTrueTime""s GPS Disciplined Cesium Oscillator Optionxe2x80x9d; Application Note #23, xe2x80x9cPrecise Synchronization of Computer Networks: Network Time Protocol (NTP) for TCP/IPxe2x80x9d; Application Note #24, xe2x80x9cPrecision Time and Frequency using GPS: A Tutorialxe2x80x9d; Application Note #25, xe2x80x9cPrecise Synchronization of Telecommunication Networksxe2x80x9d; and Application Note #26, xe2x80x9cReal Time Modeling of Oscillator Aging and Environmental Effectsxe2x80x9d. These application notes are available from TrueTime and are hereby incorporated by reference.
In addition, two-way transfer time synchronization methods may be used, including techniques similar to those described in xe2x80x9cTwo-way Satellite Time Transferxe2x80x9d.
Nevertheless, the present invention is not limited to GPS for either the master clock means nor for the device embodiment synchronization means. Any reasonably accurate clock may serve as the master clock including, but not limited to atomic clocks, cesium, rubidium, hydrogen maser clocks, or even quartz clocks, also any satellite-based clock, for example, GPS, transit navigational satellites, GOES satellites; any wireless clock, for example LORAN, TV, WWVB radio, radio phone, local radio; any land-based clock using physical interconnections such as copper wire, cable, microwave, or fiber, such as the central office clocks used currently by the telecommunications providers for synchronizing their synchronous networks; or even sea-based clocks will work as a master clock for the purposes of the present invention.
In the same way, any time synchronization techniques for synchronizing the device embodiments with a master clock and with each other may be used, such as those explained in the Logsdon reference, for example absolute time synchronization, clock fly-overs, common-view mode, and multi-satellite common view mode; those explained in the TrueTime reference, such as Network Transfer Protocol (NTP); those explained in the U.S. Naval Observatory web publication reference, such as two-way time transfer; and various other techniques in use today such as the telecommunications synchronous network system used in central offices and other higher level switching centers today.
Once a reasonably accurate time synchronization has been established in the device embodiments, well known techniques such as two-way time synchronization, common-view mode, or multi-satellite common view mode can then be used between the device embodiments in the network to measure and correct, to a high degree of accuracy, slight timing disparities and propagation delays between themselves and adjoining device embodiments. This serves to maintaining and further tighten timing synchronization.
As the device embodiments are synchronized in the network, each device initiates its own layer one event scheduling process. This process includes building a layer one event schedule which thus enables the establishment of reservations for specific times or for periodic (repeating) times for each input and output line on each network element device embodiment. In this way, packets may be scheduled to be sent from specific input lines through the non-blocking, non-delaying layer one switch to specific output lines in each network element device embodiment.
At this point, a real-time source, a real-time destination, or another network element device embodiment can initiate a layer one call setup process for any purpose, such as a real-time application or high-priority message. This process establishes a specific time or periodic (repeating) time schedule in each of the synchronized layer one network device element embodiments along a specific path from the source through the synchronized network to the destination. At the scheduled time, each synchronized layer one network element device node embodiment along that path switches their appropriate input and output lines to bypass the normal store-and-forward buffering and switching, and route directly from the input lines through a non-blocking, non-delaying layer one switch and directly on through the output lines to the next synchronized network element device node which is synchronized and scheduled to do the same thing. In this way, at any scheduled instant, a packet may be sent in a cut-through manner directly from the source through the network to the destination with only the propagation delay of the transmission lines, the input and output bypass circuitry, and the layer one circuitry. This obtains the goal of a rapid, consistent, immediate, on-time, non-blocked, non-delayed, non-congested, loss-less, jitter-free, reliable flow of data in real-time, with guaranteed delivery and guaranteed quality of service.
The network element device embodiments comprise input and output switching means; input and output buffer means controlling means; non-blocking, non-delaying layer one switching means; and optionally, a packet-oriented, cell-oriented, frame-oriented, or other store-and-forward switching means.
The first network element device embodiment is the preferred embodiment in which a standard packet, cell, or frame oriented switching means is both included and integrated into the device embodiment, such that these device embodiments are deployed in standard packet, cell, or frame-oriented networks. In this scenario, the device embodiments normally operate in packet, cell, or frame-oriented mode using the packet, cell, or frame-oriented switch. However the device embodiments are then used to schedule and switch real-time and high-priority packets to cut-through and bypass the packet, cell, or frame-oriented switched network at the scheduled times. The control circuitry in these preferred device embodiments enables complete integration into existing packet, cell, or frame-oriented networks, including the capability to store and hold non-real-time and non-high-priority in-transit packets in buffers while the layer one switching occurs, and then resume sending the non-real-time and non-high-priority in-transit packets once the layer one switching is terminated. The control circuitry in these preferred device embodiments enables scheduled layer one switching from specific input lines to specific output lines through the non-blocking, non-delaying switch, while at the same time routing in normal packet, cell, or frame mode through the packet, cell, or frame switch for input and output lines that are not scheduled for layer one switching.
The second network element device embodiment is similar to the first network device embodiment, except that the standard packet, cell, or frame-oriented switching means is not integrated into the device embodiment as one complete integrated unit. Instead, the packet, cell, or frame-oriented switch is physically distinct, and the layer one network element device embodiment is xe2x80x9coverlaidxe2x80x9d or placed around the existing packet, cell, or frame-oriented switch. In this way, all external input and output lines going to and from the network route first through the second network element device embodiment and then are connected to the physically separate store-and-forward switch. The primary purpose of the second device embodiment is to enable the installation of layer one switching on top of existing store-and-forward switches in an existing network, to eliminate the costs of replacing the existing packet, cell, or frame-based switches.
As in the first device embodiment, the second device embodiment operates normally by switching standard store-and-forward packets through to the separate and distinct packet, cell, or frame-oriented switch. Like the first device embodiment, the second device embodiment also uses its layer one switch and control circuitry to schedule and switch real-time and high-priority packets to cut-through and bypass the store-and-forward network at the scheduled times. However, in this device embodiment, the control circuitry is not integrated into the packet, cell, or frame-oriented switch. Consequently, there is the capability to stop, store, and hold standard packets in the input buffers when there is a layer one switching conflict. However, because of the physically separate store-and-forward switch, there is no control capability to force the store-and-forward switch to stop, store, and hold standard packets while the layer one switching occurs through the output stage, and then resume sending the standard packets when the layer one switching is terminated. Instead, the layer one circuitry in the second device embodiment is modified so that the output from the store-and-forward switch automatically routes to an output buffer which it can control, such that no layer one collisions will occur in the output circuitry as well.
In a third device embodiment of the invention (not shown in the drawings as it merely deletes functionality from the second device embodiment), the costs and functionality of the second device embodiment of the invention are reduced even further, by xe2x80x9cdummying it down,xe2x80x9d such that the input buffers are eliminated entirely from the third device embodiment. The primary purpose of the third device embodiment is to lower the layer one switching costs such that installation of layer one switching on top of existing store-and-forward switches in an existing network is very cost-compelling.
As in the second device embodiment, the third device embodiment operates normally by switching standard store-and-forward packets through to the separate and distinct packet, cell, or frame-oriented switch. Like the second device embodiment, the third device embodiment also uses its layer one switch and control circuitry to schedule and switch real-time and high-priority packets to cut-through and bypass the store-and-forward network at the scheduled times. However, as in the second device embodiment, there is no control circuitry integrated into the packet, cell, or frame-oriented switch and there are no input buffers. Consequently, there is no capability to stop, store, and hold standard packets in the input stage when there is a layer one switching conflict. Instead, the layer one control circuitry in this third device embodiment theoretically may interrupt standard incoming store-and-forward packets in order to execute scheduled layer one switching from specific input lines to specific output lines. Should this theoretical interruption occur, a standard packet may be lost. If loss of the packet would occur, it would likely be re-sent through its normal protocol flow control. In actual practice, however, if the clock timing of the third device embodiment is closely synchronized to the layer one device that is transmitting the layer one packets, the likely event is that very few bits would be lost on the preceding, incoming standard packet. In fact, if any bits were lost on the incoming line, they would most likely be the trailing flag bits, frame delimiter bits, or synchronization bits, from the preceding standard packet. As long as the end of frame, packet, or cell is recognized by the input circuitry of the separate store-and-forward switch, the devices will function normally. As stated previously, should any loss of standard packets, cells, or frames occur, in most cases the protocols would re-transmit the missing data.
In a fourth device embodiment of the invention (not shown in the drawings as it merely deletes functionality from the second device embodiment), the costs and functionality of the third device embodiment of the invention are reduced even further, by xe2x80x9cdummying it way downxe2x80x9d, such that the input and output buffers are eliminated entirely from the fourth device embodiment. The primary purpose of the fourth device embodiment is to significantly lower the layer one switching costs such that installation of layer one switching on top of existing store-and-forward switches in an existing network is extremely cost-compelling.
As in the third device embodiment, the fourth device embodiment operates normally by switching standard store-and-forward packets through to the separate and distinct packet, cell, or frame-oriented switch. Like the third device embodiment, the fourth device embodiment also uses its layer one switch and control circuitry to schedule and switch real-time and high-priority packets to cut-through and bypass the store-and-forward network at the scheduled times. However, as in the third device embodiment, there is no control circuitry integrated into the packet, cell, or frame-oriented switch and there are no input or output buffers. Consequently, there is no capability to stop, store, and hold standard packets in the input or output stages when there is a layer one switching conflict. Instead, the layer one control circuitry in this fourth device embodiment in practice will possibly interrupt standard incoming store-and-forward packets and will likely interrupt standard outgoing store-and-forward packets in order to execute scheduled layer one switching from specific input lines to specific output lines. When this practical interruption occurs, a standard packet will likely be lost. If loss of the packet occurs, it would also likely be re-sent through its normal protocol flow control. The fourth embodiment is not recommended, but could be used to implement very inexpensive layer one devices on top of existing store-and-forward networks, where highly cost-effective real-time or high-priority switching is desired at the understood expense of retransmitting the standard bursty, non-periodic, non-time-sensitive, lower priority store-and-forward traffic.
The fifth device embodiment consists of placing the same device elements in the Source and/or Destination device, such that the Source and/or Destination device outside of the network edge node is also outfitted with a master clock synchronization means, controlling means, input and output bypass switching and buffering means, normal packet, cell, or frame input and output circuitry means, and real-time (layer one) input and output circuitry means.
The sixth device embodiment is an extension of the fifth device embodiment, in that the layer one end-user functionality may be adapted to a Local Area Network (LAN) such as Ethernet or Token Ring by using the fifth device embodiment or xe2x80x9cend-userxe2x80x9d embodiment as the LAN controller, LAN bridge and/or LAN router, and either using the master clock and timing synchronization means to synchronize each LAN-attached device directly or having each LAN-attached device synchronize off of the synchronized clock on the LAN controller, bridge, and/or router. Modifying the software such that (a) all the LAN-attached devices have synchronized clocks, (b) each LAN-attached device keeps track of the other LAN-attached devices"" scheduled times, and (c) all LAN-attached devices do not attempt normal LAN operation when a layer one event is scheduled for another LAN-attached device, thus enables each device on the LAN to send and receive layer one packets directly and still keep normal LAN operation when layer one events are not scheduled. Each LAN-attached device can then send a layer one call setup message requesting a layer one scheduled time. Each network element on the layer one path would attempt to set up the call or session as with any other layer one setup. This would not require a need to modify the basic protocol. In effect, the basic protocol would be suspended for the layer one scheduled time. In this way, applications like Internet phone could send and receive scheduled layer one packets through the bridge or router, and out into any layer one network to any layer one connected destination. This approach would also work on intranets so that calls could be made within the LAN or intranet itself.
The seventh device embodiment does not include a standard packet, cell, or frame-oriented switching means, such that these device embodiments only switch packets in an entirely and exclusively layer one scheduled network.
The layer one Event Scheduling process comprises a layer one Call Setup Process, a layer one Switching Process, a layer one Inter-Node Call Setup Process, and a layer one Call TearDown Process. The layer one Call Setup Process schedules a layer one Event along a path of layer one device embodiments through a layer one network. The layer one Switching process switches the layer one packets through the layer one network at the scheduled times. The layer one Inter-Node Call Setup Process establishes calls between layer one device embodiments in the network for purposes of time synchronization, rapid call setups, emergencies, administration, etc. The layer one TearDown Process terminates layer one calls and frees up the layer one Scheduling process for other layer one calls.
Further, the layer one Event Scheduling Process has various Reject Mode handling capabilities that it can implement if it cannot successfully set up a call. Some examples of Reject Mode include sending a Reject Message back to the previous node thereby canceling setup of the call, enabling the node device embodiment to try an alternate route; or determining the next best scheduled time that fits into the original parameters on the Call Setup Request.
Finally, the process by which the layer one switching system works is achieved in the following steps:
Step 1xe2x80x94All routers set their clocks to exactly the same time, within some extremely small acceptable tolerance so that small variations are insignificant compared to the bit rate of the routers and transmission systems. Once the clocks are synchronized, all routers then measure or compute the approximate transmission delay times between themselves and their adjacent routers, as explained later.
Step 2xe2x80x94Real-time or high-priority Source 1 sends a call setup message to Departure Router 2 indicating that it wants to set up a real-time or high-priority layer one transmission to real-time or high-priority Receiver 5. This message may notify the Departure Router 2 that this is the first of a long stream of packets whose delivery is time-dependent and should not be subject to router, buffer, multiple paths, or other packet network delays. Included in this notification should be a minimum of the requested bit rate for the data and the requested periodicity.
Step 3xe2x80x94Departure Router 2 looks at the intended destination and requested data rate in the call setup message. Just as it does in standard packet switching, it determines that the next router is Mid-destination Router 3 and the transmission path is Transmission Path 12. Departure Router 2 then looks at Transmission Path 12""s data rate and compares it to the requested data rate from real-time or high-priority Source 1. Departure Router 2 then determines how frequently and for what duration it should send packets of data from real-time or high-priority Source 1 over Transmission Path 12 to Mid-destination Router 3. This determination is based upon data rates and pre-existing layer one schedules/reservations that may already be in existence. Based upon this determination, Departure Router 2 reserves exact times and durations for it to send information over Transmission Path 12 to Mid-destination Router 3. It then sends a call setup message to Mid-destination Router 3 telling it that it is requesting to reserve/schedule a real-time or high-priority transmission, along with the appropriate source address, destination address, its preferred departure times and duration time from Departure Router 2, and its estimated arrival times at Mid-destination Router 3.
Step 4xe2x80x94The Mid-destination Router 3 receives the call setup message from Departure Router 2. Router 3 looks at the source, destination, and requested data rate. It determines that the next router is Final Destination Router 4 using Transmission Path 13. It then looks at its own schedule, the transmission delay times, the calculated arrival times and duration time of the data that is to come from Departure Router 2. Mid-destination Router 3 then tries to schedule its physical-layer or layer one switching mechanism to effectively xe2x80x9chardwirexe2x80x9d route the stream straight on through to the Final Destination Router 4. If there is a scheduling conflict due to an existing schedule, Mid-destination Router 3 may use various Reject Modes to try to accommodate the data by buffering and delaying it very slightly. If this can""t be done with only a slight delay, Mid-Destination Router 3 may determine a reservation/schedule that works better for it. It reserves those times and communicates back to Departure Router 2 its suggested changes to the original schedule. It also may at this time notify Final Destination Router 4 what it is trying to do to determine what unreserved/unscheduled time Final Destination Router 4 might have available. This information is passed back to Departure Router 2. In this way the routers may negotiate an acceptable reservation/schedule that works for all of them.
If no schedule is acceptable, then the Departure Router 2 notifies the real-time or high-priority Source 1 that it has been unable to set up a guaranteed real-time or high-priority layer one reservation. Real-time or high-priority Source 1 can then decide if it wants to: (a) use standard packet switching with all of the inherent delays, (b) wait until the reservation/schedule frees up from other sessions which will complete and tear down their reservations/schedules soon, or (c) begin a standard packet switching session with the hope that a guaranteed real-time or high-priority reservation/schedule will become available during the session as other real-time or high-priority sessions are completed and torn down. In situation (c) a standard packet switching style session can be converted to a guaranteed on-time real-time or high-priority layer one session once the reservation/scheduling arrangements can be made, even during the course of a session, if desired.
Step 5xe2x80x94Final Destination Router 4 repeats the process described in Step 4, communicating its reservation/schedule back to Departure Router 2 and Middestination Router 3 until an acceptable reservation/schedule is set up between them. Final Destination Router 4 then notifies the Real-time or high-priority Receiver 5 that a session is being established. In this way the Real-time or high-priority Receiver 5 gets ready to accept Real-time or high-priority data input.
Step 6xe2x80x94Once the reservation/scheduling is agreed upon, Departure Router 2 notifies real-time or high-priority Source 1 to start shipping data. Departure Router 2 then ships the data to Mid-destination Router 3 over Transmission Path 12 at exactly the agreed upon time. Mid-destination Router 3 is ready and waiting for the data at exactly the calculated arrival time and xe2x80x9chardwirexe2x80x9d layer one switches the data straight on through to Final Destination Route 4 over Transmission Path 13 at precisely the correct times. Final Destination Route 4 then xe2x80x9chardwirexe2x80x9d layer one switches the data straight on through to the Real-time or high-priority Receiver 5 over Transmission Path 14.
Step 7xe2x80x94When the session has no more data to ship, for example, the streaming program is completed, or the phone call is xe2x80x9chung upxe2x80x9d, then the reservation/schedule for that session needs to be torn down. This event can be triggered by a TearDown notification message from either of the end routers to the routers along the path. Once a router receives notification that the session is over, it tears down that session, wherein it frees up its reservation schedule, and reverts to standard packet network mode until another guaranteed real-time or high-priority session is requested and negotiated, which starts the process all over again.
It is accordingly an object of the present invention to guarantee high-quality, rapid, consistent, on-time, non-blocked, non-delayed, non-congestion-affected, loss-less, jitter-free, reliable delivery of packets in a packet network, for real-time, high-priority, and/or high-quality-of service applications that require it. It does this in the following ways: (a) It assures delivery of the packets in order without being discarded or dropped as in normal packet, cell, or frame switching. (b) It delivers the packets on time by scheduling arrival times and departure times. (c) It reduces delays by skipping the queuing mechanisms in the routers. (d) It eliminates the need for large buffers, thereby reducing or eliminating long start delays and awkward pauses. (e) It reduces significantly or entirely eliminates jitter by delivering packets at known, predictable times.
Thus the overall benefits of the invention are:
It establishes a means to deliver packets, cells, or frames over a packet switched network in a way that guarantees that they will be delivered on-time and in time to be used by the receiving application. This means that packets won""t be lost or arrive too late to be used by the application.
It reduces the overall delay time for real-time applications such as voice, video, and other real-time multimedia delivery needs over a packet network. This will reduce or eliminate the noticeable xe2x80x9clag-timexe2x80x9d for Internet Phone. It also will reduce or eliminate the delayed start times in xe2x80x9cstreamingxe2x80x9d audio and video, because the receiver doesn""t need to wait to fill its huge incoming buffer.
It can be used as a prioritization and advanced reservation scheme, thus assuring high priority users that they can have the capacity needed at a particular time.
It solves the non-guaranteed, random, lossy degraded, and delayed response time problems of packet, cell, and frame-based networks for real-time applications, high-priority messages, and high-quality-of-service.
It works with standards based protocols and networks, e.g., RIP, OSPF, RSVP, ISA, IGMP (multicast), ATM, TCP/IP, Ethernet, Token Ring, X.25, Frame Relay, SMDS.
It thus creates the capability for a Next Generation of routers and/or software
Throughout this disclosure, various devices, methods, and systems are described in various manners using various descriptive terms. Thus, for purposes of understanding the context, scope, and clarity of the present disclosure, the following definitions are provided.
The term switching as used in the present invention describes multiple functions including, but not limited to the origination of data (as in a source network element); the reception of data (as in a destination network element); the transfer of data directly through a network element (as in pure layer one switching); and the reception, storage, and retransmission of data through a network element (with buffering). Consequently, the term switching in the present invention is defined as comprising at least, but is not limited to, one or more of the following operations: transferring, transferring to, transferring from, transferring over, transferring between, transmitting, communicating, sending, receiving, retransmitting, broadcasting, multicasting, uni-casting, switching, routing, relaying, storing, retrieving, forwarding, storing-and-forwarding, bypassing, passing through, tunneling, tunneling through, cutting through, and/or any other method of moving information either into a device, out of a device, or through a device.
The terms transmitting and transmission, as used in the present invention, are also used to describe the origination of data (as in a source network elementxe2x80x94transmit from); the reception of data (as in a destination network elementxe2x80x94received transmission); the transfer of data directly through a network element (as in pure layer one switchingxe2x80x94transmitted through); and the reception, storage, and retransmission of data through a network element (with bufferingxe2x80x94transmitted through). Thus, the terms transmitting and transmission are defined as comprising at least, but are not limited to, one or more of the following operations: transferring, transferring to, transferring from, transferring over, transferring between, transmitting, communicating, sending, receiving, retransmitting, broadcasting, multicasting, uni-casting, switching, routing, relaying, storing, retrieving, forwarding, storing-and-forwarding, bypassing, passing through, tunneling, tunneling through, cutting through, and/or any other method of moving information either into a device, out of a device, or through a device.
Information is defined as at least, but not limited to data communicable over a network. Information comprises, but is not limited to one or more of the following types of data: data that has been formatted in a packet, cell, or frame; data that has a header; data in which a header has been removed or replaced; voice data; video data; telephony data; video conferencing data; computer data; computer host data; computer network data; local area network data; stored data; retrieved data; scheduled data; guaranteed data; layer one data; layer two data; layer three data; layer four data; phone data; Internet phone data; packet phone data; Internet video conferencing data; video streaming data; audio streaming data; multimedia data; multimedia streaming data; broadcast data; multicast data; point-to-point data; emergency message data; time-dependent data; network control data; guaranteed delivery data; important data; urgent data; and/or any other data associated with layer one switching. Information also comprises data associated with, but not limited to, one or more of the following applications: browsers, web browsers, browser applications, graphics, viewers, electronic mail, voice, voice mail, video, video conferencing, shared white-boarding, analog to digital conversion, digitization, compression, packetization, de-packetization, de-compression, digital-to-analog conversion, real-time applications, computer applications, computer host applications, computer network applications, storage applications, storage network applications, database applications, retrieval applications, scheduled applications, guaranteed delivery applications, high-priority applications, Quality of Service (QoS) applications, Class of Service (CoS) applications, Type of Service (ToS) applications, layer one applications, layer one session applications, phone applications, Internet phone, Internet phone applications, packet phone applications, Internet video conferencing, video streaming, audio streaming, multimedia, multimedia streaming applications, broadcast applications, multicast applications, emergency system applications, time-sensitive applications, time-dependent applications, network control applications, guaranteed delivery applications, important information applications, and urgent information applications.
Information also comprises, but is not limited to, data associated with one or more of the following protocols: any data network protocols, computer network protocols, local area network protocols, Ethernet protocols, token ring protocols, internet protocols, intranet protocols, IP protocols including TCP/IP protocols and UDP/IP protocols, asynchronous transfer mode (ATM) protocols, X.25 protocols, routing protocols, routed protocols, voice over IP protocols, voice mail protocols, storage network protocols, database protocols, retrieval network protocols, store-and-forward protocols, frame relay protocols, resource reservation protocols, bit stream reservation protocols, layer one protocols, layer two protocols, layer three protocols, layer four protocols, higher layer protocols, call or session setup protocols, call or session teardown protocols, cut-though protocols, flow protocols, asynchronous protocols, synchronous network protocols, and/or any other network or communication protocols.
A network element and/or device is defined as at least, but not limited to, one or more elements, components, subcomponents, mechanisms, sub-mechanisms, systems, subsystems, processors, nodes, and/or any other devices used in, attached to, or associated with a network of any sort. Network elements may comprise at least, but are not limited to, one or more of the following elements, components, subcomponents, mechanisms, sub-mechanisms, systems, subsystems, processors, nodes, and/or devices: pure layer one embodiments, layer two elements, layer three elements, layer four elements, end user embodiments, overlay embodiments, integrated embodiments, local area network embodiments, cut-through embodiments, source elements, destination elements, departure elements, combinations of source elements with other network elements, combinations of destination elements with other network elements, originating edge node elements, departure node elements, mid-destination elements, final destination elements, terminating edge node elements, and/or any other elements, components, subcomponents, mechanisms, sub-mechanisms, systems, subsystems, processors, nodes, or any other devices used in a network of any sort.
Network elements and/or devices may comprise at least, but are not limited to, one or more of the following devices, instruments, apparatus, mechanisms, and/or functional components: communications devices; telecommunications devices; data communications devices; hybrid network devices; network-attached devices; local area network-attached devices, such as local area network controllers, local area network bridges, local area network routers, local area network switches, and/or local area network hubs; browser devices; web browser devices; graphics devices; electronic mail devices; voice devices; video devices; video conferencing devices; real-time devices; end-user devices; computer devices; computer host devices; server devices; processor devices; microprocessor devices; integrated circuit devices; computer network devices; storage devices; retrieval devices; storage area network devices; memory devices; database devices; switching devices; routing devices; workstations; bridges; hubs; wireless devices; scheduled devices; guaranteed delivery devices; high-priority devices; layer one devices; phone-oriented devices, such as Internet phone devices, packet phone devices, private branch exchanges (PBXs), and telephone instruments; Internet video conferencing devices; video streaming devices; audio streaming devices; multimedia devices; multimedia streaming application devices; broadcast application devices; multicast application devices; emergency system application devices; time-sensitive application devices; time-dependent application devices; network control application devices; guaranteed delivery application devices; important information application devices; urgent information application devices; interconnection devices; gateways to other networks; and/or any other device, instrument, mechanism and/or functional component used in, associated with, and/or attached to a network of any sort.
Network elements and/or devices may be operable in at least, but not limited to, one or more of the following networks: communications networks, telecommunications networks, data communications networks, local area networks, Ethernet local area networks, ring-style local area networks, token-style local area networks, star-type local area networks, point-to-point networks, loop networks, arbitrated loop networks, multi-drop bus networks, fabric networks, voice networks, video networks, video conferencing networks, real-time networks, computer networks, processor networks, microprocessor networks, storage networks, retrieval networks, storage area networks, database networks, server networks, switching networks, routing networks, store-and-forward networks, cut-through networks, scheduled networks, guaranteed delivery networks, high-priority networks, layer one networks, phone networks, private branch exchange (PBX) networks, Internet phone networks, packet phone networks, Internet video conferencing networks, video streaming networks, audio streaming networks, multimedia networks, multimedia streaming networks, broadcast networks, multicast networks, emergency system networks, time-sensitive networks, time-dependent networks, network control networks, guaranteed delivery networks, important information networks, hybrid networks, urgent information networks, and/or any other networks which may be adapted to functionally carry out layer one switching.
Network elements and/or devices may be operable using at least, but not limited to, one or more of the following protocols: any data network protocols, computer network protocols, local area network protocols, Ethernet protocols, token ring protocols, internet protocols, intranet protocols, IP protocols including TCP/IP protocols and UDP/IP protocols, asynchronous transfer mode (ATM) protocols, X.25 protocols, routing protocols, routed protocols, voice over IP protocols, voice mail protocols, storage network protocols, database protocols, retrieval network protocols, store-and-forward protocols, frame relay protocols, resource reservation protocols, bit stream reservation protocols, layer one protocols, layer two protocols, layer three protocols, layer four protocols, higher layer protocols, call or session setup protocols, call or session teardown protocols, cut-though protocols, flow protocols, asynchronous protocols, synchronous network protocols, and/or any other network or communication protocols.
Network elements and/or devices may be associated with at least one or more of the following applications: browsers, web browsers, browser applications, graphics, viewers, electronic mail, voice, voice mail, video, video conferencing, analog to digital conversion, digitization, compression, packetization, de-packetization, de-compression, digital-to-analog conversion, real-time applications, computer applications, computer host applications, computer network applications, storage applications, storage network applications, database applications, retrieval applications, scheduled applications, guaranteed delivery applications, high-priority applications, Quality of Service (QoS) applications, Class of Service (CoS) applications, Type of Service (ToS) applications, layer one applications, layer one session applications, phone applications, Internet phone, Internet phone applications, private branch exchange (PBX) applications, packet phone applications, Internet video conferencing, video streaming, audio streaming, multimedia, multimedia streaming applications, broadcast applications, multicast applications, emergency system applications, time-sensitive applications, time-dependent applications, network control applications, guaranteed delivery applications, important information applications, and/or urgent information applications.
Network elements and/or devices may comprise and/or be associated operationally with at least one or more of the following elements and/or components: microprocessors, processors, integrated circuits, application specific integrated circuits, programs, memory, program memory, stored memory, random access memory (RAM), memory devices, storage, storage devices, queues, buffers, shift registers, and switches.
The terms synchronizing and synchronization are defined as comprising at least, but are not limited to, one or more elements, mechanisms, methods and/or schemes for establishing, coordinating, and/or maintaining timing in one or more network elements and/or devices. Synchronizing and synchronization may be achieved by, but are not limited to, utilizing one or more of the following elements, mechanisms, methods, and/or schemes: master clock; central clock; receiver clock; Global Positioning System; differential Global Positioning System; synchronization transmitter; synchronization receiver; synchronization transmission media; atomic clocks; cesium clocks; rubidium clocks; hydrogen maser clocks; quartz clocks; satellite-based clocks; transit navigational satellite clocks; GOES satellite clocks; telecommunications synchronous network systems; wireless clocks; LORAN clocks; TV clocks; WWVB radio clocks; radio phone clocks; local radio clocks; land-based clocks with physical interconnections such as copper wire, cable, microwave or fiber; central office clocks; sea-based clocks; any other accurate clocks; in-band synchronization; out-of-band synchronization; local area network synchronization clocks; pulses; master pulses; propagation delay; pulses plus propagation delay; synchronization pulses; synchronization pulses on transmission lines; synchronization signals; wireless synchronization pulses; synchronization bits; synchronization bits from one or more packets; synchronization packets; synchronization cells; synchronization frames; loose synchronization; close synchronization; synchronization within a safety zone time window; synchronization by comparison of expected packet, cell, or frame arrival time to actual packet, cell, or frame arrival time; synchronization based on previous packet, cell, or frame arrival time; common mode time transfer; absolute time synchronization; relative time synchronization; clock fly-overs; common-view mode; multi-satellite common view mode; time-stamped clock information; time codes; two-way time transfer; one-way time transfer; Network Transfer Protocol; Network Time Protocol; Real Time Protocol; and any other elements, mechanisms, methods and/or schemes used for establishing, coordinating, and/or maintaining timing in one or more network elements and/or devices.
A synchronization component is defined as at least, but not limited to, one or more elements and/or mechanisms used for synchronization of one or more distributed network elements or devices. Synchronization components may comprise at least, but are not limited to, one or more of the following elements and/or mechanisms: master clock; central clock; Global Positioning System; differential Global Positioning System; synchronization transmitter; synchronization receiver; synchronization transmission media; atomic clocks; cesium clocks; rubidium clocks; hydrogen maser clocks; quartz clocks; satellite-based clocks; transit navigational satellite clocks; GOES satellite clocks; telecommunications synchronous network systems; wireless clocks; LORAN clocks; TV clocks; WWVB radio clocks; radio phone clocks; local radio clocks; land-based clocks with physical interconnections such as copper wire, cable, microwave or fiber; central office clocks; sea-based clocks; any other accurate clocks; in-band synchronization; out-of-band synchronization; local area network synchronization clocks; pulses; master pulses; propagation delay; pulses plus propagation delay; synchronization pulses; synchronization pulses on transmission lines; synchronization signals; wireless synchronization pulses; synchronization bits; synchronization bits from one or more packets; synchronization packets; synchronization cells; synchronization frames; loose synchronization; close synchronization; synchronization within a safety zone time window; comparison of expected packet, cell, or frame arrival time versus actual packet, cell, or frame arrival time; synchronization based on previous packet, cell, or frame arrival time; and/or any other elements or mechanisms used for synchronization of one or more distributed network elements or devices.
A reservation schedule is defined as at least, but not limited to, one or more elements and/or mechanisms used to reserve one or more times for the operation of switching, transferring, transmitting, bypassing, or receiving information. A reservation schedule may comprise at least, but is not limited to, one or more of the following elements and/or mechanisms: one or more specific times; one or more absolute times; one or more relative times; one or more periodic times and/or periodic time intervals; one or more repeating times; one or more non-periodic times; one or more start times; one or more completion and/or end times; one or more sources and/or one or more destinations, which may include internal ports or addresses as well as external ports or addresses; and availability status for said times, said sources, and/or destinations, such as available, unavailable (reserved), or tentatively scheduled. An example of a reservation schedule, specifically an example of a layer one event schedule is shown in FIG. 37. The terms open and opening are defined as establishing a direct layer one physical connection through one or more network elements.
The terms close and closing are defined as disconnecting a direct layer one physical connection through one or more network elements.
A layer one connection is defined as a physical connection into, out of, through, or around a device and/or network element at a physical layer one level. Said layer one connection is determined based upon time as opposed to header information, although header information may be used for call setup and in the originating edge node. A layer one connection may or may not include buffering.
Connection media into and out of layer one switching devices and/or network elements may comprise one or more of, but is not limited to, the following connection media: electrical media, wire media, copper wire media, cable media, coaxial cable media, microwave media, wireless media, optical media, and fiber media.
The terms store-and-forward switching, store-and-forward switch, and/or store-and-forward switching component, as used in the present invention refer to any layer two or higher-layer packet-based, cell-based, or frame-based data switching network element, device, instrument, apparatus, mechanism, and/or component. Store-and-forward switching, store-and-forward switches, and/or store-and-forward switching components may comprise at least, but are not limited to, one or more of the following layer two or higher-layer network elements, devices, instruments, apparatus, mechanisms, and/or components: communications devices; telecommunications devices; cut-through switches; cut-through devices; data communications devices; hybrid network devices; network-attached devices; local area network-attached devices, such as local area network controllers, local area network bridges, local area network routers, local area network switches, and/or local area network hubs; browser devices; web browser devices; graphics devices; electronic mail devices; voice devices; video devices; video conferencing devices; real-time devices; end-user devices; computer devices; computer host devices; server devices; processor devices; microprocessor devices; integrated circuit devices; computer network devices; storage devices; retrieval devices; storage area network devices; memory devices; database devices; switching devices; routing devices; workstations; bridges; hubs; wireless devices; scheduled devices; guaranteed delivery devices; high-priority devices; phone-oriented devices, such as Internet phone devices, packet phone devices, private branch exchanges (PBXs), and telephone instruments; Internet video conferencing devices; video streaming devices; audio streaming devices; multimedia devices; multimedia streaming application devices; broadcast application devices; multicast application devices; emergency system application devices; time-sensitive application devices; time-dependent application devices; network control application devices; guaranteed delivery application devices; important information application devices; urgent information application devices; interconnection devices; gateways to other networks; and/or any other layer two or higher-layer device, instrument, and/or mechanism used in, associated with, or attached to a network of any sort.
Store-and-forward switching, store-and-forward switches, and/or store-and-forward switching components may comprise at least, but are not limited to, one or more of the following layer two or higher-layer network protocols: any data network protocols, computer network protocols, local area network protocols, Ethernet protocols, token ring protocols, internet protocols, intranet protocols, IP protocols including TCP/IP protocols and UDP/IP protocols, asynchronous transfer mode (ATM) protocols, X.25 protocols, routing protocols, routed protocols, voice over IP protocols, voice mail protocols, storage network protocols, database protocols, retrieval network protocols, store-and-forward protocols, frame relay protocols, resource reservation protocols, bit stream reservation protocols, layer two protocols, layer three protocols, layer four protocols, higher layer protocols, call or session setup protocols, call or session teardown protocols, cut-though protocols, flow protocols, asynchronous protocols, synchronous network protocols, and/or any other layer two or higher-layer network or communication protocols.
Layer one switching circuitry is defined as circuitry capable of establishing a physical layer one connection into, out of, through, and/or around a network element. Layer one switching circuitry may or may not include buffering and various input to output switching components. Layer one switching circuitry may comprise a non-blocking, non-delaying switching fabric; but it may also comprise a blocking and/or delaying switching fabric. In addition, when used with buffering and other input and output switching elements, the layer one switching circuitry may be caused to act like a non-blocking, non-delaying switch layer one switch; or it may be caused to act like a blocking and/or delaying layer one switch.
Bypass switching circuitry is defined as circuitry capable of establishing a physical connection and/or a layer one connection into, out of, through, and/or around a layer two or higher-layer device and/or network element. Bypass switching circuitry may or may not include buffering. Bypass switching utilizes layer one switching circuitry. Bypass switching circuitry may utilize separate switching fabric from the layer two and/or higher-layer device it bypasses; or the bypass switching circuitry may utilize the same switching fabric as the layer two or higher-layer switching circuitry, such that a single switching fabric is used for both functions, which may also be called layer one cut-through switching or layer one tunneling.